package base.demo;

import base.utils.PrintUtils;

import java.util.Arrays;

public class ShellSortDemo {

    static int[] array = {49, 38, 65, 97, 76, 13, 27, 31, 49, 78, 34, 12, 21, 64, 46, 1};

    public static void main(String[] args) {
        shellSortPiece6(array);
    }

    public static void mySort() {

        int[] array = {49, 38, 65, 97, 76, 13, 27, 31, 49, 78, 34, 12, 21, 64, 46, 1};

        //希尔排序
        int gap = array.length;
        while (true) {
            gap = gap / 2;   //增量每次减半
            for (int i = 0; i < gap; i++) {

                for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
                    int temp = array[j];
                    int k = j - gap;                //相当于得到  i (j=i+gap)
                    while (k >= 0 && array[k] > temp) {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = temp;
                }

            }
            if (gap == 1) break;
        }
        PrintUtils.print(array);
    }


    public static void shellSortPiece() {

        int[] array = {49, 38, 65, 97, 76, 13, 27, 31, 49, 78, 34, 12, 21, 64, 46, 1};
        PrintUtils.print(array);
        //希尔排序
        int gap = array.length;
        while (true) {
            gap = gap / 2;   //增量每次减半
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
                    int temp = array[j];
                    int k = j - gap;
                    while (k >= 0 && array[k] > temp) {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = temp;
                }
            }
            if (gap == 1) break;
        }
    }

    public static void shellSortPiece3(int[] arr) {

        //希尔排序
        int gap = arr.length;
        int len = arr.length;
        while (true) {
            gap = gap / 2;
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < len; j += gap) {
                    int tmp = arr[j];
                    int k = j - gap;
                    while (k >= 0 && arr[k] > tmp) {
                        arr[k + gap] = arr[k];
                        k -= gap;
                    }
                    arr[k + gap] = tmp;
                }
            }
            if (gap == 1) break;
        }
    }

    public static void shellSortPiece4(int[] arr) {
        //希尔排序
        int gap = arr.length;
        int len = arr.length;
        while (true) {
            gap = gap / 2;
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < len; j += gap) {
                    int tmp = arr[j];
                    int k = j - gap;
                    while (k >= 0 && arr[k] > tmp) {
                        arr[k + gap] = arr[k];
                        k -= gap;
                    }
                    arr[k + gap] = tmp;
                }
            }
            if (gap == 1) break;
        }
    }

    public static void shellSortPiece5(int[] arr) {
        //希尔排序
        int gap = arr.length;
        int len = arr.length;
        while (true) {
            gap = gap / 2;
            for (int i = 0; i < gap; i++) {
                for (int j = i; j < len; j += gap) {
                    int tmp = arr[j];
                    int k = j;
                    while (k > gap - 1 && arr[k - gap] > tmp) {
                        arr[k] = arr[k - gap];
                        k -= gap;
                    }
                    if (k != j) arr[k] = tmp;
                }
            }
            if (gap == 1) break;
        }
        PrintUtils.print(arr);
    }

    public static void shellSortPiece2() {
        int len = array.length;
        int gap = array.length;
        while (true) {
            gap = gap / 2;
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < len; j += gap) {
                    int tmp = array[j];
                    int k = j - gap;
                    while (k >= 0 && array[k] > tmp) {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = tmp;
                }
            }
            if (gap == 1) break;
        }
    }

    public static void shellSortPiece6(int[] arr) {
        int len = arr.length;
        int gap = arr.length;

        while (true) {
            gap = gap / 2;
            for (int i = 0; i < gap; i++) {
                for (int j = i; j < len; j += gap) {
                    int k = j;
                    int tmp = arr[j];
                    while (k > gap - 1 && tmp < arr[k - gap]) {
                        arr[k] = arr[k - gap];
                        k -= gap;
                    }
                    if (k != j) arr[k] = tmp;
                }
            }
            if (gap == 1) break;
        }
    }


}
































